Batch 2 - Class 316 - Hat Puzzles II

• (in class)

• There are 4 prisoners, three standing in a queue, but the fourth is in a separate room (no one can see him, and he can't see anyone else) - there are two white and two black hats. They must shout out their hat color as soon as they know what it is. Who is the first person to shout out and why? https://www.youtube.com/watch?v=DMDzHlFMIAU
• If 2 and 3 have the same color, then 1 will shout out first. If 1 doesn't shout out, then 2 knows that his hat color is different from 3, and hence will shout out.

• (Khan Academy) 10 prisoners are given a chance of survival by the jailer. The jailer tells them that the next morning, he will have them stand in a queue (so that the last person can see the nine people in front, the second last people can see eight people in front of him, and so on), and then place either a red hat or a purple hat on each person's head. The person hence will be able to see the color of hat for people in front of him (but not his own hat). The jailer will then start from the last person, and ask each person "What is the color of hat on your head". The person can answer "red" or "purple". If the person's answer is correct, he will be released, else he will be killed. The jailer will then ask the same question to the second last person, and so on. The prisoners have the night to figure out the strategy so that maximum number of prisoners can survive (on a guaranteed basis). Figure out a strategy to save the maximum number of prisoners.
• Answer: "Last guy calls the odd number of hats in front". Every person there on keeps a count of odd or even parity.

• What if there weren't just two colors of hats, but 5. Or 10?
• Answer: Now instead of odd and even parity, they could assign colors numbers 0..4 and then use the sum mod 5
• The prisoner now has 11 hats each of a different color, randomly removes one of the hats and then shuffles the rest and places it on prisoners' heads. He also mandates that no one can repeat a color that has already been said. https://www.youtube.com/watch?v=7hJ4Azr--s8
• Answer: The first person sees two missing hats. He says the sum of those modulo 10. Suppose he says 7 - it could mean that 1 and 6 are missing, or 2 and 5 are missing, or 3 and 4 are missing, or 8 and 9 are missing. However, for the next person in front, she is missing 3 numbers, so just has to total the three numbers modulo 10, and the difference with the first spoken number tells her her hat number. Every person continues in that manner, except when it comes to the person whose hat number is 7. She can not repeat 7, but since she knows one of the missing hat number (or the hat of the first person), she can say that. So all but two are saved.

• In the above problem, what if people in front know what people at the back said, but dont know if they survived or died? So when someone whose hat was number 7 said 1 (assuming 1 was missing), the remaining people dont know if that answer was right or wrong? In that case, the person with hat number 7 can just say the number of the person in front. Whenever someone sees a person saying a number which they can obviously see, they know that that number was spoken wrong. The last person doesn't know this and can die. So total 3 people dead.

• Ten gnomes again stand in a line, back-to-front, each with a hat—rouge or puce—placed on his head. The color of each gnome’s hat is determined by the toss of a coin (and the gnomes know this). Each gnome can see the colors of the hats in front of him. Starting at the back of the line, each gnome is asked, in turn, to either make a guess as to the color of his hat or say PASS. If any single gnome makes an incorrect guess, all will be immediately executed. If all gnomes say pass, all will be executed. The gnomes will only survive if at least one guess is made and all guesses offered are correct. What strategy could the gnomes agree upon to ensure them a maximal probability of survival? (Assume that each gnome can hear the guess made behind him.)